package java学习.代码随想录.动态规划;

import java.util.*;

/**
 * **************
 * 项目名称: 蓝桥杯-Java学习 <br/>
 * 文件名称:  <br/>
 * 文件描述: 这里添加您的类文件描述，说明当前文件要包含的功能。 <br/>
 * 文件创建：刘世锦Lenovo <br/>
 * 创建时间: 2022/9/1 <br/>
 *
 * @version v1.0 <br/>
 * @update [序号][日期YYYY-MM-DD][更改人姓名][变更描述]<br/>
 * *************
 */
public class 打家劫舍III {
    /**
     * Definition for a binary tree node
     */

    /**
     * 每个节点可选择偷或者不偷两种状态，根据题目意思，相连节点不能一起偷
     *
         * 当前节点选择偷时，那么 其两个孩子节点就不能选择偷了
         * 当前节点选择不偷时，两个孩子节点只需要拿最多的钱出来就行(两个孩子节点偷不偷没关系)
     *
     * 链接：https://leetcode.cn/problems/house-robber-iii/solution/san-chong-fang-fa-jie-jue-shu-xing-dong-tai-gui-hu/
     */
    public static int rob1(TreeNode root) {

        int[] result = byArray(root);
        return Math.max(result[0],result[1]);
    }

//    a[0]: 不偷 = max(left[1]+right[0],left[0]+right[1]) 选择一个最大的
//    a[1]: 偷  = root.val + left[0]+right[0]
    private static int[] byArray(TreeNode root) {
        int[] arr = new int[2];
        if (root == null) return arr;
        int[] left = byArray(root.left);
        int[] right = byArray(root.right);
//        后序遍历： 通过左右孩子来确定 根节点 是否偷
//        不偷root： 开始偷孩子节点 可以考虑偷
        arr[0] = Math.max(left[0],left[1])+Math.max(right[1],right[0]) ;
//        偷root： 选取root 且不能偷 孩子节点。
        arr[1] = root.val+left[0]+right[0];
        System.out.println(Arrays.toString(arr));
        return arr;
    }


    public static int rob(TreeNode root) {

        if (root==null){
            return 0;
        }
        int money = root.val;
//        max(  儿子 , 爷爷+孙子 )
        /**    2
            3     4
           1  5  2  4
         1  2  3   4  1
         */
        if (root.left!=null){
            TreeNode left = root.left;
            money+=rob(left.left)+rob(left.right);
        }
        if (root.right!=null){
            money+=rob(root.right.right)+rob(root.right.left);
        }

        return Math.max(money,rob(root.left)+rob(root.right));
    }
    static Map<TreeNode,Integer> map =    new HashMap<TreeNode,Integer>();

    public static int robDP(TreeNode root) {

        if (root==null){
            return 0;
        }
        if (map.containsKey(root)){
            return map.get(root);
        }
        int money = root.val;
//        max(  儿子 , 爷爷+孙子 )
        /**    2
         3     4
         1  5  2  4
         1  2  3   4  1
         */
        if (root.left!=null){
            TreeNode left = root.left;
            money+=robDP(left.left)+robDP(left.right);
        }
        if (root.right!=null){
            money+=robDP(root.right.right)+robDP(root.right.left);
        }
        int result =  Math.max(money,robDP(root.left)+robDP(root.right));
        map.put(root,result);
        return result ;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        TreeNode l = new TreeNode(2);
        root.left = l;
        TreeNode r = new TreeNode(3);
        root.right = r;
        l.right = new TreeNode(3);
        l.left = null;
        r.left = null;
        r.right = new TreeNode(1);
//        func(root);
    }
}

 class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}